/*
 * heapBasics.hpp
 *
 *  Created on: Sep 21, 2011
 *      Author: dgdiniz
 */

#ifndef HEAPBASICS_HPP_
#define HEAPBASICS_HPP_

#include "utility/utility.hpp"

namespace playlib
{


template<typename T>
void heapSiftDown(T list[], unsigned start, unsigned end)
{
	unsigned child, root, swp;

	root = start;

	while (root*2+1 <= end)
	{
		child = root*2+1;
		swp = root;

		if (list[root] < list[child]) swp = child;
		if ((child+1 <= end) && (list[swp] < list[child+1])) swp = child+1;

		if (swp != root)
		{
			swap(list[root], list[swp]);
			root = swp;
		}
		else return;
	}
}


template<typename T>
void heapify(T list[], unsigned size)
{
	int start = size/2-1;

	while (start >= 0)
	{
		heapSiftDown(list, start, size-1);
		start--;
	}
}


}

#endif /* HEAPBASICS_HPP_ */
